package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;
import com.lun.util.SinglyLinkedList.ListNode;

public class ConvertSortedListToBinarySearchTree {
	public TreeNode sortedListToBST(ListNode head) {
		if (head == null)
			return null;
		return sortedListToBST(head, null);

	}

	public TreeNode sortedListToBST(ListNode head, ListNode tail) {
		ListNode slow = head;
		ListNode fast = head;
		if (head == tail)
			return null;

		while (fast != tail && fast.next != tail) {
			fast = fast.next.next;
			slow = slow.next;
		}
		TreeNode thead = new TreeNode(slow.val);
		thead.left = sortedListToBST(head, slow);
		thead.right = sortedListToBST(slow.next, tail);
		return thead;
	}

}
